//瓦片BBOX
//用法：构造瓦片BBOX，瓦片唯一索引转X,Y，瓦片唯一索引转坐标，X,Y转唯一索引，坐标转唯一索引
//用法：按最小代价搜索路径，获取从某点出发的“路径代价地图”

var TileBox = function(netType, xSize, ySize, res, spacerate) {
	this.xSize = xSize;
	this.ySize = ySize;
	this.tileCount = xSize * ySize;
	this.neighborCache = [];
	
	var sprite = new cc.Sprite(res);
	var space = spacerate || 0.5;
	
	this.tileWidth = sprite.width;
	this.tileHeight = sprite.height;
		
	this.width = (1 + xSize + 2 * space) * this.tileWidth;
	this.height = (0.5 + ySize + 2 * space) * 0.75 * this.tileHeight;
	
	this.tileNet = new TileNet(netType, this.tileWidth, this.tileHeight,
			this.tileWidth * (space + 0.5), this.tileHeight * (space + 0.5));
	
	this.IndexToTile = function(index){
		var yid = Math.floor(index / this.xSize);
		return {x: index - ( yid * this.xSize), y: yid };
	};

	this.TileToIndex = function(tile){
		return tile.y * this.xSize + tile.x;
	};
	
	this.IndexToCoord = function(index){
		return this.tileNet.TileToCoord(this.IndexToTile(index));
	};

	this.CoordToIndex = function(coord){
		return this.TileToIndex(this.tileNet.CoordToTile(coord));
	};
	
	this.TileInBox = function(tile){
		return tile.x > -1 && tile.y > -1 && tile.x < this.xSize && tile.y < this.ySize;
	};

	this.CoordInBox = function(coord){
		return this.TileInBox(this.tileNet.CoordToTile(coord));
	};
	
	for (var idx = 0; idx < this.xSize; idx++) {
		for (var idy = 0; idy < this.ySize; idy++) {
			var tile = {x:idx, y:idy};
			var index = this.TileToIndex(tile);
			var neighbor_rough = this.tileNet.NeighborTileXYs(tile);
			var neighbor = [];
			for (var jdx in neighbor_rough){
				if (neighbor_rough[jdx].x > -1
						&& neighbor_rough[jdx].y > -1
						&& neighbor_rough[jdx].x < this.xSize
						&& neighbor_rough[jdx].y < this.ySize){
					neighbor[neighbor.length] = this.TileToIndex({x:neighbor_rough[jdx].x, y:neighbor_rough[jdx].y});
				}
			}
			this.neighborCache[index] = neighbor;
		}
	}

	//callback should be function(tgtTileIndex, neighborId)
	this.foreachNeighbor = function(index, callback){
		if (!callback)
			return;

		for (var idx in this.neighborCache[index]){
			callback(this.neighborCache[index][idx], idx);
		}
	};

	//Belows are about search route
	this._node = null;
	this._CreateNode = function(pay,previous,next,root,waited)
	{
		return {
			pay: pay,
			previous: previous,
			next: next,
			root: root,
			waited: waited
		};
	};
	this._CreateNodeArray = function(){
		this._node = new Array(this.tileCount);
		for (var idx = 0; idx < this.tileCount; idx++){
			this._node[idx] = this._CreateNode(32767, idx-1, idx+1, -1, true);
		}
		this._node[this.tileCount-1].next = -1;
	};
	this._MoveStartToHead = function(startIndex){
		if (startIndex != 0){
			this._node[this._node[startIndex].previous].next = this._node[startIndex].next;
			if (this._node[startIndex].next != -1)
				this._node[this._node[startIndex].next].previous = this._node[startIndex].previous;

			this._node[startIndex].previous = -1;
			this._node[startIndex].next = 0;
			this._node[0].previous = startIndex;
		}
	};
	this._MovePlace = function(ptr, preptr){
		if (preptr != -1){
			if (this._node[ptr].previous != -1)
				this._node[this._node[ptr].previous].next = this._node[ptr].next;
			if (this._node[ptr].next != -1)
				this._node[this._node[ptr].next].previous = this._node[ptr].previous;

			this._node[ptr].previous = preptr;
			this._node[ptr].next = this._node[preptr].next;
			 
			this._node[this._node[preptr].next].previous = ptr;
			this._node[preptr].next = ptr;
		}
	};
	this._FindValidNode = function(ptr){
		var currentptr = this._node[ptr].previous;
		if (this._node[currentptr].pay <= this._node[ptr].pay)
			return -1;
		while (this._node[currentptr].pay > this._node[ptr].pay){
			currentptr = this._node[currentptr].previous;
		}
		return currentptr;
	};

	this.RoutePay_def = function()
	{
		//将节点全部纳入搜索队列，并赋所有节点代价为32767
		//将起始点排列到队列头
		//设置起始点当前代价为0
		//设置当前节点为起始点

		//while (当前节点非null，且非目标节点)
		{
			//标记当前节点为已搜索
			//for 搜索当前节点的邻节点
			{
				//if (邻节点非已搜索)
				{
					//计算代价值:pay
					//if (pay小于邻节点的当前代价值)
					{
						//邻节点的当前代价值赋为pay
						//邻节点的根节点赋为当前节点
						//将邻节点的队列位置前移，直到其前一个节点的代价值<pay
					}
				}
			}
			//当前节点赋为队列下一节点
		}
		//if (当前节点为null)
		{
			//输出null
		}
		//else
		{
			//输出 路径    输出格式：{ pay:pay, route:route }  route为从终点到始点的tileIndex队列
		}
	};
	
	// costmap : 代价地图，两个点间的移动代价为两个点的代价之和，如果某点代价小于0，则不可到达
	// startindex, endindex : 起点和终点
	// bool_route : 是否输出路径
	// 输出格式：{ pay:pay, route:[tileId1, tileId2, ...] }  route为"!从终点到始点!"的tileIndex队列
	this.RoutePay = function(costmap, startindex, endindex, bool_route){
		if (costmap[startindex] == -1 || costmap[endindex] == -1){
			return { pay:-1, route:[] };
		}
		
		this._CreateNodeArray();
		this._MoveStartToHead(startindex);
		this._node[startindex].pay = 0;
		var currentptr = startindex;
		while (currentptr != -1 && currentptr != endindex){
			this._node[currentptr].waited = false;
			
			for (var neighborid in this.neighborCache[currentptr]){
				var tileIndex = this.neighborCache[currentptr][neighborid];
				if (this._node[tileIndex].waited && costmap[tileIndex] >= 0){
					var pay = this._node[currentptr].pay + costmap[currentptr] + costmap[tileIndex];
					if (pay < this._node[tileIndex].pay){
						this._node[tileIndex].pay = pay;
						this._node[tileIndex].root = currentptr;
						this._MovePlace(tileIndex, this._FindValidNode(tileIndex));
					}
				}
			}

			currentptr = this._node[currentptr].next;
		}
		if (currentptr == -1){
			return { pay:-1, route:[] };
		}
		else{
			var pay = this._node[currentptr].pay;
			route = [];
			if (bool_route){
				for (var index = 0; currentptr != startindex; currentptr = this._node[currentptr].root, index++){
					route[index] = currentptr;
				}
				route[route.length] = startindex;
			}
			return { pay:pay, route:route };
		}
	};
	
	// costmap : 代价地图，两个点间的移动代价为两个点的代价之和，如果某点代价小于0，则不可到达
	// startindex : 起点
	// maxpay : 计算的最大代价
	// 输出格式：[{pay:pay1,root:preTileIndex1},{pay:pay2,root:preTileIndex2},....]，一共N个tile。
	// 超过maxpay的点为:{pay:-1,root:-1}
	// 每个tile包含pay和root，pay为pay，root为"从起始点抵达该节点的路径"的上一节点。
	this.MapPay = function(costmap, startindex, maxpay){
		if (costmap[startindex] < 0)
			return CreateArray(0, costmap.length, {pay:-1, root:-1}, false);
		
		this._CreateNodeArray();
		this._MoveStartToHead(startindex);
		this._node[startindex].pay = 0;
		var currentptr = startindex;
		while (currentptr != -1 && this._node[currentptr].pay <= maxpay){
			this._node[currentptr].waited = false;
			
			for (var neighborid in this.neighborCache[currentptr]){
				var tileIndex = this.neighborCache[currentptr][neighborid];
				if (this._node[tileIndex].waited && costmap[tileIndex] >= 0){
					var pay = this._node[currentptr].pay + costmap[currentptr] + costmap[tileIndex];
					if (pay < this._node[tileIndex].pay){
						this._node[tileIndex].pay = pay;
						this._node[tileIndex].root = currentptr;
						this._MovePlace(tileIndex, this._FindValidNode(tileIndex));
					}
				}
			}
			
			currentptr = this._node[currentptr].next;
		}
		var paymap = new Array(this._node.length);
		for (var tmpid in this._node){
			if (this._node[tmpid].pay <= maxpay)
				paymap[tmpid] = {pay:this._node[tmpid].pay, root:this._node[tmpid].root};
			else
				paymap[tmpid] = {pay:-1, root:-1};
		}
		return paymap;
	};
	
	this._LogAll = function(){
		for (var ydx = 0; ydx < 9; ydx++){
			var str = "";
			for (var xdx = 0; xdx < 11; xdx++){
				str += this._node[ydx*11 + xdx].previous + "," + this._node[ydx*11 + xdx].pay + "\t";
			}
			cc.log(str);
		}
		cc.log("=========================================================");
	}
}